Talk:Rayo's number/Archive 1
Need upper and lower bounds for the more rigorous definition of this number... Ikosarakt1 (talk) 12:31, July 19, 2012 (UTC) :The formal definition of this number is found in a cited source. In all honesty, I can't make much sense of it. FB100Z • talk • 20:28, July 19, 2012 (UTC) :Correct me if I'm wrong, but couldn't the fast growing hierarchy be defined within first order set theory? Is so, how can a growth rate within the fast growing hierarchy be specified? How was this result obtained, or where did it come from? Sbiis Saibian (talk) 00:18, January 20, 2013 (UTC) :This article may be helpful for you. Ikosarakt1 (talk) 13:43, January 22, 2013 (UTC) :Thank you for the resource. I have never seen this guy's work before. It seems there are many "googologist's" on the internet, even if they aren't aware of the term or the fact that there is at least one community of googologist's. I have been wondering what the largest well defined number is (let's not quibble like the mathematicians over the well foundedness of such a concept -_-), or more correctly, what the fastest growing well defined paradigm is for sometime. I have heard of oracle turing machines, but I wasn't sure whether that was still included within first order set theory or not. I was also not sure how much of ordinal notation (and consequently how much of the fast-growing hierarchy) was included. There are also a few other miscellaneous concepts which I haven't gotten around to deciding which is stronger. I will have to bookmark these articles and give them a good read. It appears that this guy, at least for the moment, is the champion by all reasonable measures. :Sbiis Saibian (talk) 15:22, January 22, 2013 (UTC) : Corrected strength of function In cimments to this post me and A.P.Goucher concluded, that actual strength of Rayo's function is nuch larger than \(\omega^\text{CK}_1 \times \omega\). It is at level of \(\omega^\text{CK}_\omega\). First few values What do you think, is it possible to evaluate (or prove lower bounds) small values of Rayo(n)? Ikosarakt1 (talk) 10:07, January 30, 2013 (UTC) :Even the definition of ℜ(n'') is enough to make my head hurt, let alone the size of ℜ( ). FB100Z • talk • 19:43, February 5, 2013 (UTC) :My guess is that Rayo(10) is the smallest value that has a definition. To my knowledge, it's not possible to force the value of x1 with less than 10 symbols. Bounds If we use the naive method of defining the ordinals, by putting 0 in variable 2, 1 in variable 3, 2 in variable 4, etc. we can define a very weak, but rigorous lower bound for Rayo(n). * Defining "(¬∃1(1∈2))" (10 symbols) puts a 0 in x2. * Defining "(1∈2∧(¬∃1(1∈3∧(¬1=2))))" (23 symbols) puts a 1 in x3. * Defining "(2∈3∧(¬∃1(1∈4∧((¬1=2)∧(¬1=3)))))" (32 symbols) puts a 2 in x4. * Defining "(3∈4∧(¬∃1(1∈5∧((¬1=2)∧((¬1=3)∧(¬1=4))))))" (41 symbols) puts a 3 in x5. * etc. * AND-ing together ''n expressions takes an additional 3''n'' - 3 symbols. * 0 takes at most 10 symbols. * 1 takes at most 3 + 23 symbols. * 2 takes at most 6 + 23 + 32 symbols. * 3 takes at most 9 + 23 + 32 + 41 symbols. * etc. Therefore the number of symbols it takes to Rayo-name n'' is at most (9n2 + 43n)/2. This gives the lower bound Rayo(10100) >> 4.7140×1049. FB100Z • talk • 22:33, February 5, 2013 (UTC) Does the variable 10 count as 1 symbol or 2? Also, (2∈1∧(¬∃3(3∈1∧(¬3∈2∧(¬3=2))))) makes 1 the successor of 2. Now we only have to use a linear number of characters to define numbers instead of it having to take a quadratic number of characters. Therefore Rayo(10100) >>3.333x1098. Tomtom2357 (talk) 14:27, June 10, 2013 (UTC) :In set theory each number is abstract concept, not composition of digits. Each number counts as one symbol. LittlePeng9 (talk) 18:09, June 10, 2013 (UTC) These bounds don't give the grasp how large Ra(10^100) is. It would be nice to show that \(Ra(10^{100}) > S_{BB}(n)\) (for any reasonable n), where \(S_{BB}(n)\) is similar to Bird's \(S(n)\) function (described in his currently last part of array notations), but the rule M1 is replaced by \(\{a,b\} = \Sigma(b,a)\). Ikosarakt1 (talk ^ ) 14:41, June 10, 2013 (UTC) I'm having a bit of trouble defining addition using set theory. I'm sure once I get how to use recursive definitions, I'll be able to construct large numbers very quickly. Also, my expression above is incomplete, it ensures that the set 1 contains 2 and it does not contain any element that is not 2 or a member of 2. The correct expression is: 2∈1∧¬∃3(3∈1∧¬3∈2∧¬3=2)∧¬∃3(¬3∈1∧3∈2). I now know how to define the subset operation, ¬∃3(¬3∈1∧3∈2) states that 2 is a subset of 1. I can also define the union of 2 sets 2 and 3: ¬∃4(¬4∈1∧4∈2)∧¬∃4(¬4∈1∧4∈3)∧¬∃4(4∈1∧¬4=2∧¬4∈3) (makes 1 the union of 2 and 3). Actually, I can define the union of any set of sets: ¬∃3,4(3∈2∧4∈3∧¬4∈1)∧¬∃3(3∈1∧¬∃4(3∈4∧4∈2)) (1 is the union of all sets in 2). Tomtom2357 (talk) 06:03, June 11, 2013 (UTC) Make the page about him itself. You can make the page about him like sbiiss saibian and the peoples. Jiawheinalt (talk) 11:28, February 14, 2013 (UTC) Rayo's number is much larger! Apparently, in a blog post a few months ago, A.P. Goucher made the claim that Rayo's number was at the level of the order-\(\omega\) Busy Beaver function (and there at the level of \(\omega^\text{CK}_\omega\) in the fast-growing hierarchy, although this association has issues of its own). He therefore concluded that his Xi function grew faster. These statements have been repeated several times in this wiki. However, it is incorrect. The trouble is that Goucher got the definition of Rayo's number wrong. The correct definition is, per the wiki article, "the smallest number bigger than any finite number named by an expression in the language of first order set theory with a googol symbols or less." Goucher, however, defined it as "the largest integer expressible uniquely by ''n symbols in first-order logic". He then goes on to define first-order logic, but what he is actually defining is first-order arithmetic. Now, the "largest integer expressible uniquely by n'' symbols in first-order arithmetic" is indeed on the order of the order-\(\omega\) Busy Beaver function. But second order arithmetic is much, much stronger; it is measured by Turing hyperjumps, which are on a completely different level from the Turing jumps of first-order arithmetic. So I don't think we are even equipped to measure the strength of second-order arithmetic in terms of higher order Busy Beaver functions. And first order set theory is much, much stronger than second-order arithmetic, or even nth-order arithmetic for any n. I'm not sure how strong Goucher's combinatory logic is, but it doesn't seem to have the power of second order arithmetic. So I strongly believe that Rayo's function grows much, much faster than Goucher's Xi function. After some time to allow for discussion, I will try to correct the wiki articles with the wrong information on Rayo's number. Deedlit11 (talk) 23:52, March 12, 2013 (UTC) It took me over an hour to figure out what you were talking about here. Now I think I understand. FO arithmetic is allowed to quantify over sets of numbers, while FO logic is allowed to quantify over any sets (thus, for example, we can make statements about sets of real numbers). I think even second-order arithmetic will overcome Xi function. I don't know very much about higher-order Turing jumps, but I know there is hierarchy of hyper-n-jumps for every order of arithmetics. If you are right, we'll really need new notation for such large ordinals! (provided such notation is possible!) LittlePeng9 (talk) 13:34, March 13, 2013 (UTC) oh god FB100Z • talk • 18:31, March 13, 2013 (UTC) @LittlePeng9, I'm not aware of hyper-n-jumps for n > 1. Where did you hear about them? Interestingly, while Turing jumps take you through the arithmetical hierarchy (the hierarchy for first order arithmetic), Turing hyperjumps do not in fact take you through the analytical hierarchy (the hierarchy for second order arithmetic). In fact, if S is a Delta-1-2 set, then the hyperjump of S is a Delta-1-2 set as well. So hyperjumps do not even take you out of Delta-1-2 sets, which is quite early in the hierarchy. Second order arithmetic is quite strong! Deedlit11 (talk) 21:31, March 13, 2013 (UTC) Well, I'm not entirely sure where I heard about them; it may be unconfirmed information as well. And yes, SO arithmetic is very strong, that's why most people use restricted induction/comprehension - there is no ordinal notation known strong enough to measure strength of this system! LittlePeng9 (talk) 22:06, March 13, 2013 (UTC) Goucher has agreed that, when quantification is over sets (which it is in the case of Rayo's function), Rayo's function will exceed his Xi function. So perhaps we can start removing references to Rayo's function being less than the Xi function or at the \(\omega_{\omega}^{CK}\) level of the fast-growing hierarchy. Deedlit11 (talk) 02:28, March 21, 2013 (UTC) I think that if first order logic indeed can define fast-growing hierarchy, then Rayo's function must have order type \(\omega_1\) or above, since \(\omega_1\) is actually limit ordinal for the fast-growing hierarchy (which can't be defined without fundamental sequences). Ikosarakt1 (talk ^ ) 18:49, May 9, 2013 (UTC) I don't even think that \(\omega_1\) function is possible. And first-order logic has only countably many sentences, so if we could somehow code functions in it there would be only countably many functions. Rayo's function can't be strictly stronger than diagonalization of all these functions, and diagonalizing through countably many countable ordinals gives still countable ordinal. Similar argument works for any consistent logic theory, so we can't find single consistent theory containing whole FGH. This doesn't hold for inconsistent theories, though. English language, for example, has no limit ordinal (as if it had, sentence "smallest order type larger than all provable ordinals is ordinal" would be provable). English is inconsistent, really. LittlePeng9 (talk) 19:24, May 9, 2013 (UTC) :In that case, I shall remove the sentence that FGH is probably definable in first order logic. Ikosarakt1 (talk ^ ) 08:47, May 10, 2013 (UTC) ::You can define the FGH up to a given ordinal in first order logic, but to do so you need to define the ordinal. Of course, you can't define \(f_{\omega_1}\) using a fundamental sequence, since the fundamental sequence of \(\omega_1\) is uncountable - but you may be able to define a function for \(f_{\omega_1}\) that surpasses \(f_\alpha\) for all countable \(\alpha\). Whether or not it is possible to define the FGH up to \(\omega_1\) so that no function surpasses the entire hierarchy is independent of ZFC. Deedlit11 (talk) 01:10, May 11, 2013 (UTC) Rayo's function - end of googology? Is it possible to create a function growing faster than Rayo's function? I read there is a problem with ordinal notation to create a more fast-growing functions.Konkhra (talk) 10:41, March 15, 2013 (UTC) Even though Rayo(n) is growing very fast asymptotically, I can't understand the size of this number without relations with other known functions. It would be nice to know on what values overtakes tetration, pentation, Ackermann function, ..., up to uncomputable functions such as \(\Sigma(n)\) or even \(\Sigma_2(n)\). Ikosarakt1 (talk ^ 11:14, March 15, 2013 (UTC) Konkhra, there is no fastest growing function anyways. Take, say, Rayo(2n), Rayo(n^2), or even Rayo(Rayo(n)), Rayo(Rayo(Rayo(n)))), Rayon(n). Googology can't end because there are infinitely many numbers greater than Rayo's number. Ikosarakt1 (talk ^ 11:39, March 15, 2013 (UTC) If I'm not mistaken, we can ask questions about largest integer nameable in 2nd order logic (by quantifying over finite formulas. LittlePeng9 (talk) 13:45, March 15, 2013 (UTC) :Yes, we could do that, and it should get us larger numbers. Another thing we could do is add a truth predicate to the language; this will allow us to define Rayo(n) within the language, so we get fundamentally larger numbers. We can add another truth predicate that tells us whether a formula within the stronger language is true, and iterate through the ordinals. So the question is, which is stronger, going to higher order logics, or iterating truth predicates? Deedlit11 (talk) 02:00, March 20, 2013 (UTC) :Second order logic is able to define first order truth predicate. Third order logic can define second order one etc. So higher order logic is at least as strong as iterated truth predicates, and I guess it's strictly stronger. LittlePeng9 (talk) 06:27, March 20, 2013 (UTC) ::is it difficult get larger numbers with use 2nd order logic? I have never read of such numbers. These numbers have not yet created? Konkhra (talk) 05:09, March 22, 2013 (UTC) What about taking advantage of type theory? I know loader.c has done some limited form of that. FB100Z • talk • 06:40, March 22, 2013 (UTC) : This may work. Especially if we allow quantification over types. LittlePeng9 (talk) 17:26, March 22, 2013 (UTC) Will I break the world record if I define the function \(Ra(a,b)\) to be the largest number that can be expressed using a symbols in b-th order set theory, and then propose the number \(Ra(\text{meameamealokkapoowa oompa},\text{meameamealokkapoowa oompa})\)? Ikosarakt1 (talk ^ 15:55, March 22, 2013 (UTC) :Define \(b\)-th order set theory. FB100Z • talk • 17:05, March 22, 2013 (UTC) :::I don't know the exact definition, but we can replace it with b-th order logic. First order logic allows quantification over sets. Define by induction n+1-th order logic as extension of n-th order logic with quantification over formulas of n-th order logic (let's call them n-formulas). :::Now a question - can we extend this definition transfinitely? \(\omega \)-th order logic would allow quantification over n-formulas for all (finite) n. Generally, \(\alpha \)-th order logic allows quantification over any \(\beta <\alpha \)-formulas. This definition may be vague or may cause inconsistency (but I don't think it does, it disallows self-quantification) but seems legit. LittlePeng9 (talk) 17:19, March 22, 2013 (UTC) ::::Based on what I've read, order-\(\omega\) logic is actually type theory... FB100Z • talk • 18:20, March 22, 2013 (UTC) :::::Hmm, all the type theory systems I'm familiar with are computable, so they wouldn't generate functions faster growing than the Busy Beaver function. Wikipedia distinguishes logic from type theory, but perhaps there are type theory systems with comparable power. Deedlit11 (talk) 02:05, March 23, 2013 (UTC) ::::::It looks like I need to read up on my metamathematics. Does anyone have any websites, books, etc. they recommend? FB100Z • talk • 02:43, March 23, 2013 (UTC) :::::::Well, I learned set theory from "Set Theory: An Introduction to Large Cardinals" by Frank Drake, and recursion theory from "Theory of Recursive Functions and Effective Computability" by Hartley Rogers. As for type theory, I've recently been reading this paper: http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf It's on the untyped lambda calculus, but it relates to typed systems. Deedlit11 (talk) 02:39, March 24, 2013 (UTC) ::::::::Okay, I'll scour the local library for those and related books. This is not the kind of stuff they teach me in high school, sadly... FB100Z • talk • 05:58, March 26, 2013 (UTC) Loader's number I wonder how the output from loader.c compares to Rayo's number? --Ixfd64 (talk) 05:10, March 26, 2013 (UTC) :It's the output of a 512 character C computer program, so it's clearly less than BB_C (512), where BB_C is the Busy Beaver function for C programs. Note that BB_C(n) grows no faster than BB(n). I believe that BB(n) > BB_C(n), so Loader's number would be less than BB(512), and probably less than BB(100). Rayo's number is in a whole different universe. Deedlit11 (talk) 05:41, March 26, 2013 (UTC) ::I see. I had initially expected it to be roughly comparable to BB(512), but this post led me to think it would be much larger. I guess it would probably be more in the neighborhood of TREE(3), etc. --Ixfd64 (talk) 16:24, March 26, 2013 (UTC) ::@Deedlit11 If BB(n)BB(512). You probably meant reverse inequality. All I know is that there exists number a, such that BB_C(a*n)>BB(n), because C is able to emulate TM. I think adding one state requires around 100 symbols, so a is around that large. ::@lxfd64 I don't think it's that large. I guess it's expressable using \(\Gamma_0\) LittlePeng9 (talk) 16:40, March 26, 2013 (UTC) :::You're right, I had the inequality reversed. I don't think there is a number a such that BB_C(a*n) > BB(n) - to describe a state of an n-state Turing machine requires O(log n) characters, so we need \(a n \log(n)\) characters to emulate an n-state Turing machine. So I imagine that BB(n) ~ BB_C(an log(n)). :::Loader's number is much greater than TREE(3) or even SGC(13) - his function is not provably recursive in nth-order arithmetic for any n, so it corresponds to a very large recursive ordinal. Deedlit11 (talk) 23:22, March 27, 2013 (UTC) ::::perhaps Loader's number larger then SCG(SCG... (SCG(13))...) with for example googol nested functions? Konkhra (talk) 23:31, March 27, 2013 (UTC) :::::Yes, certainly. Iterating a function is just one level up the fast-growing hierarchy from the original function, so when you have two functions at significantly different ordinals, the faster one will still be faster than iterations of the slower one. Deedlit11 (talk) 00:08, March 28, 2013 (UTC) ::::Sorry, but I'm a little confused. Letting BB(n) ≈ BBC(a * log(n)) suggests that the output would be around BB(167), assuming a ≈ 100 and that we're using the natural log. However, I'm having doubts that BB(167) would be larger than SCG(13). Or does the busy beaver function really grow so fast so early? --Ixfd64 (talk) 03:19, March 28, 2013 (UTC) :::::One thing I've learned about the busy beaver function — that f***er is ''fast. FB100Z • talk • 06:39, March 28, 2013 (UTC) :::::That is, as Sbiis Saibian noted "that before you would reach BB(100) the resourcefulness of the human imagination would be overwhelmed". I'll agree him, there are \(\approx 1.889 \times 10^{521}\) TM's to verify, well over a centillion. Ikosarakt1 (talk ^ 12:56, March 28, 2013 (UTC) :::::Actually, that should be BB(n) ≈ BBC(an * log(n)), there's a factor of n in there. Assuming the size of the largest output is proportional to the number of programs, we want xx ≈ 128y. Setting y = 512, we get x ≈ 412. I imagine that 400-500 states is a reasonable number of states to try to program a TM that computes SGC(n). But I suspect BB(n) passes SGC(13) _much_ earlier. It is hard to program a TM that gets any near the Busy Beaver function; for example, if you asked someone to program repeated exponentiation, I imagine it would take considerably more than 6 states, but a 6-state machine implementing repeated exponentiation was indeed found. It seems not unreasonable that BB(100) is larger than any number we have dreamt up using recursive processes. I certainly believe that about BB(1000). Deedlit11 (talk) 07:27, March 29, 2013 (UTC) :::::The problem is that there are a lot of TMs with chaotic behavior. Usually namely these machines are busy beavers. By the way, on the Robert Munafo's site I found the formula that generates lesser number of TMs than usual. Therefore, the number of 100-state TMs to verify (if we exclude the trivial ones) are about \(3.211 \times 10^{517}\). Even the number of them is much larger than the number of Planck volumes in the observable universe. Ikosarakt1 (talk ^ 11:22, March 29, 2013 (UTC) ::::Sorry, I had busy day, I made two fails. Yes, loader's number may indeed be that large, for then I thought about D(D(99)). I managed to write body to emulate TM in C++ (it shouldn't be far apart from C form). It needs 205 non-blank characters for body and at most 38+4log_10(s) characters to add new state (where s is number of states). If anyone is interested, I can post code on pastebin. LittlePeng9 (talk) 10:23, March 28, 2013 (UTC) So we can state that the BB(167) is greater than SCG(13). in this case, the lower bound for BB(167) was found! Konkhra (talk) 00:06, March 29, 2013 (UTC) :Sorry, but this isn't rigorous proof. I found when BB_C is larger than BB, but to be sure we have to find strict inverse relation. Not to mention proving SCG(13)∨ (ψ = "→ i" ∧ x_{x_i}) to the definition. Would this be too powerful? FB100Z • talk • 01:35, April 25, 2013 (UTC) Growth rate of Rayo's function Can we say that for example Ra(10) is greater than BB(100) or BB(1000) or it is not known? Konkhra (talk) 10:13, May 5, 2013 (UTC) Dubious - I don't think that it is possible to define \(\Sigma(n)\) with merely 10 symbols. Ikosarakt1 (talk ^ ) 10:24, May 5, 2013 (UTC) Yes, Rayo's function has very slow start. In most formulations 0 is empty set, and this formula: (¬∃2(2∈1)) defines empty set. Also, no other set can be uniquely defined in 10 symbols. So Ra(10)=0\Sigma(n)\)? Ikosarakt1 (talk ^ ) 13:00, May 5, 2013 (UTC) Well, n you ask for must be pretty large. We need hundreds of characters to define useful recursion. Before that point best we can do is explained in article. Say we can define recursion with 500 characters in Rayo's micro-language. While BB(500) is unimaginably large, for Ra(500) we can hardly define multiplication. I guess smallest cross point of function is counted in millions, but that'll probably never be known for us. LittlePeng9 (talk) 13:33, May 5, 2013 (UTC) Number of possible expressions To prove the specific value of Ra(n), we need to sort out all expressions with n symbols. (Like we solve all \((4n+4)^{2n}\) TMs for \(\Sigma(n)\)). Through, how many these expressions for Ra(n)? This significantly depends on radix that we use. For example, if we use decimal, then string defining 0 is: (¬∃2(2∈1)) (10 symbols). Using unary, the string would look like that: (¬∃11(11∈1)) (already 12 symbols). Ikosarakt1 (talk ^ ) 13:48, May 5, 2013 (UTC) As far as I know, every integer is counted as single number, so (¬∃2(2∈1)) has 10 symbols and (¬∃11(11∈1)) is, if we take both 1's separately, is invalid expression. There is infinitely many choices for each character, but we can filter finite number from this by noting that, say, ((2∈1)∧(3∈1)) is exactly same as ((3∈1)∧(2∈1)). So if we make assumption that for largest integer n used as variable every integer FOST string names at most one positive integer. Let \(C(n)\) denote all the positive integers Rayo-nameable in \(n\) symbols or less, so that \(\text{Rayo}(n) = \max(C(n)) + 1\). There are at most \(\sum_{i = 0}^n (7 + i)^i\) strings, so \(|C(n)| \leq \sum_{i = 0}^n (7 + i)^i \leq n(7 + n)^n\). FB100Z • talk • 23:04, May 9, 2013 (UTC) There seem to be two ways to evaluate these types of functions. The first is to loop through all possible expressions, and the second is to build expressions of your own. In this case, the first solution seems nigh impossible. The second is fairly productive; it's not hard to show that Rayo's number >> 10^50. FB100Z • talk • 20:08, May 5, 2013 (UTC) :Yes, but the second way allows us only to give lower bound for Ra(n), because we're not sure that our own expression will be the solution. Ikosarakt1 (talk ^ ) 08:46, May 10, 2013 (UTC) Symbols Anyone know, or know where I can find the complete list of symbols that can be used in rayo's function? I'm going to try and make some kind of lower bounds (smallest number of symbols needed to define n) I'll assume for now that they're the same as 1st order logic. DrCeasium (talk) 13:04, June 23, 2013 (UTC)